Статья 1216

Название статьи

АГРЕГАЦИЯ УРАВНЕНИЙ В ЦЕЛОЧИСЛЕННОМb ПРОГРАММИРОВАНИИ

Авторы

Веселов Сергей Иванович, кандидат физико-математических наук, доцент, кафедра алгебры, геометрии и дискретной математики, Институт информационных технологий, математики и механики, Нижегородскийгосударственный университет имени Н. И. Лобачевского (Россия, г. Нижний Новгород, пр. Гагарина, 23), veselov@vmk.unn.ru
Чирков Александр Юрьевич, кандидат физико-математических наук, доцент, кафедра алгебры, геометрии и дискретной математики, Институт информационных технологий, математики и механики, Нижегородский государственный университет имени Н. И. Лобачевского (Россия, г. Нижний Новгород, пр. Гагарина, 23), chir7@yandex.ru
Грибанов Дмитрий Владимирович, ассистент, кафедра алгебры, геометрии и дискретной математики, Институт информационных технологий, математики и механики, Нижегородский государственный университет имени Н. И. Лобачевского (Россия, г. Нижний Новгород, пр. Гагарина, 23), dimitry.gribanov@gmail.com

Индекс УДК

519.854

DOI 

10.21685/2072-3040-2016-2-1

Аннотация

Актуальность и цели. Исследуется следующее обобщение агрегации систем линейных диофантовых уравнений: для заданной системы уравнений  Σj=1naijxj = ai, i = 1,...,m, с целыми коэффициентами найти целые множители f1,f2,...,fm такие, что вершины выпуклой оболочки множества целых неотрицательных решений этой системы являются вершинами выпуклой оболочки множества целых неотрицательных решений уравнения Σmi=1fiΣnj=1aijxj = Σmi=1fiai.
Материалы и методы. В работе используются методы линейного программирования и геометрии чисел.
Результаты. Доказано, что обобщенное агрегирующее уравнение существует для любой системы линейных уравнений. Для систем уравнений с неотрицательными коэффициентами указан простой способ вычисления чисел f1,f2,...,fm. Получена достижимая нижняя оценка свободного члена обобщенного агрегирующего уравнения. Описан класс задач целочисленного линейного программирования, сводящихся к задаче о рюкзаке с правой частью Σmi=1fiaменьшей, чем при любом способе обычной агрегации.
Выводы. Новый подход к агрегации расширяет область ее применения и уменьшает коэффициенты агрегирующего уравнения.

Ключевые слова

агрегация систем линейных уравнений, задача о рюкзаке.

Скачать статью в формате PDF
Список литературы

1. Шевченко, В. Н. Качественные вопросы целочисленного программирования / В. Н. Шевченко – М. : Наука, 1995. – 192 с.
2. Веселов, С. И. Об агрегации линейных целочисленных уравнений / С. И. Весе-лов // Кибернетика. – 1985. – № 4. – С. 58–60.
3. Plateau, G. Aggregation of equalities in integer programming / G. Plateau and M. T. Guerch // Lecture Notes in Control and Information Sciences. – 1984. – Vol. 59. – P. 183–192.
4. Бабаев, Д. А. Агрегация одного класса систем целочисленных уравнений / Д. А. Бабаев, К. Ш. Мамедов // Журнал вычислительной математики и математи-ческой физики. – 1978. – Т. 18, № 3. – С. 614–619.
5. Kannan, R. Polynomial-Time Aggregation of Integer Programming Problems / R. Kannan // Journal of the Association for Computing Machinery. – 1983. – Vol. 30, № 1. – P. 133–145.
6. Babayev, D. A. Aggregation of nonnegative integer-valued equations / D. A. Baba-yev, F. Glover // Discrete Applied Mathematics. – 1984. – Vol. 8, № 2. – P. 125–130.
7. Elimam, A. A. On the reduction method for integer linear programs, II* / A. A. Elimam, S. E. Elmaghraby // Discrete Applied Mathematics. – 1985. – Vol. 12, № 3. – P. 241–260.
8. Babayev, D. A. A New Knapsack Solution Approach by Integer Equivalent Aggre-gation and Consistency Determination / D. A. Babayev, F. Glover, J. Ryan // Informs Journal on Computing. – 1997. – Vol. 9, № 1. – P. 43–50.
9. Babayev, D. A. Sequential and simultaneous aggregation of Diophantine equations / D. A. Babayev, S. S. Mardanov // Discrete Applied Mathematics. – 1994. – Vol. 50, № 3. – P. 209–220.
10. Веселов, С. И. Об экспоненциальном росте коэффициентов агрегирующего уравнения / С. И. Веселов, В. Н. Шевченко // Кибернетика. – 1978. – № 4. – С. 78–79.

 

Дата создания: 31.08.2016 10:53
Дата обновления: 28.11.2016 13:39